package leedcode_path.treeNoDE;

public class 中序后序遍历数 {
    /*
    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

theory
habitat
struggle
     * */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length==0||postorder.length==0) return null;
        return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);


    }
    public TreeNode buildTree(int[] inorder,int inorderstart,int inorderend,int[] postorder,int postorderstart,int postorderend){

        if (postorderstart==postorderend) return null;
        TreeNode root=new TreeNode(postorder[postorderend-1]);
        int mid;
        for (mid= inorderstart; mid <inorderend ; mid++) {
            if (inorder[mid]==postorder[postorderend-1]){
                break;
            }
        }
        int leftinorderstart=inorderstart;
        int leftinorderend=mid;
        int rightinorderstart=mid+1;
        int rightinorderend=inorderend;

        int leftpostorderstart=postorderstart;
        int leftpostorderend=postorderstart+(mid-inorderstart);
        int rightpostorderstart=leftpostorderend;
        int rightpostorderend=postorderend-1;

        root.left=buildTree(inorder,leftinorderstart,leftinorderend,postorder,leftpostorderstart,leftpostorderend);
        root.right=buildTree(inorder,rightinorderstart,rightinorderend,postorder,rightpostorderstart,rightpostorderend);

        return root;





    }
}
